// 单词搜索
package Leetcode_Second_Brush;

public class Solution079 {
    public boolean exist(char[][] board, String word) {
        int row = board.length;
        int column = board[0].length;
        boolean[][] isVisit = new boolean[row][column];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (board[i][j] == word.charAt(0) && DFS(board, isVisit, word, 0, i, j)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean DFS(char[][] board, boolean[][] isVisit, String word, int cur, int i, int j) {
        if (cur == word.length()) {
            return true;
        }

        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(cur) || isVisit[i][j]) {
            return false;
        }

        isVisit[i][j] = true;

        // 定义四个方向：上、下、左、右
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int[] dir : directions) {
            int newRow = i + dir[0];
            int newCol = j + dir[1];

            if (DFS(board, isVisit, word, cur + 1, newRow, newCol)) {
                return true;
            }
        }

        isVisit[i][j] = false; // 回溯
        return false;
    }
}
